<HTML>
<HEAD>
   <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
   <META NAME="GENERATOR" CONTENT="Mozilla/4.0b3 [en] (WinNT; I) [Netscape]">
   <TITLE>Michael Maguire - Visual Matching
</TITLE>
<!-- ============================================================== -->
<!-- ====== HTML Page Template -- Michael Maguire -- 25 Oct 95 ==== -->
<!-- ============================================================== -->
<!-- ============================================================== -->
<!-- ============================================================== -->
<!-- ====== Document Title Here =================================== -->
<!-- ============================================================== -->
<!-- ============================================================== -->
</HEAD>
<BODY>

<H1>
Visual Matching</H1>

<HR>
<BR>This is a port of some educational software I wrote several
years ago for Prof. Luis Goddyn of the Centre for Experimental and Constructive
Mathematics, Simon Fraser University.  I haven't yet implemented
all the user-friendliness, animation and algorithms of the Macintosh C
versions, but the applet demonstrates some potential for Java's
use in visualization.
<BR>

<BR>For the <B>minimum weight non-bipartite perfect matching</B>, the colours don't matter --
just enter some points, then hit
step or go, and watch as the Java applet matches them up into pairs
using the minimum total line length.
<BR>
<BR>For the <B>minimum weight bipartite perfect matching</B>, enter the same
number of red and blue points in the area provided below,  watching as the Java applet finds the best way to marry all
the blue points to the red points using the minimum total line length.
<BR>
<BR>For the <B>minimum weight spanning tree</B>, the colours don't matter --
just enter some points and watch the Java applet connect them up into a
network using the minimum total line length.
<BR>
<HR WIDTH="100%">
<BR><APPLET codebase="." code="ca.michaelmaguire.client.visualalgorithms.VisualMatching.class" width=640 height=480></APPLET>
<HR WIDTH="100%">
<BR>The algorithms are based on some work in <I>Geometric Duality and
Combinatorial Optimization</I> by M. Juenger, Universitaet zu Koeln and
W.R. Pulleyblank, IBM T. J. Watson Research Center.
<BR>
<BR>Note: This applet was compiled with Sun's JDK javac 1.6.0_17 with compiler compliance set to 1.3.  The source for the site and the applet can be found at <a href="http://code.google.com/p/visualalgorithms/">http://code.google.com/p/visualalgorithms/</a>. 
<BR>
<BR>
<HR WIDTH="100%">
<BR>
See also the version being used in courses at Simon Fraser University: 
<A HREF="http://www.math.sfu.ca/~goddyn/Courseware/Visual_Matching.html">http://www.math.sfu.ca/~goddyn/Courseware/Visual_Matching.html</A>
<BR>
<BR>
<HR WIDTH="100%">
<ADDRESS>
<A HREF="http://www.facebook.com/m.a.maguire">Michael
Maguire</A></ADDRESS>

<BR><!-- ============================================================== --><!-- ======== last modified date here ============================= --><FONT SIZE=-1>04
Jan 2010 <!-- ============================================================== --><!-- ============================================================== --></FONT> 

</BODY>
</HTML>
